package model;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import model.BalanceObjective.BalancePair;

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

import etm.core.configuration.EtmManager;
import etm.core.monitor.EtmMonitor;
import etm.core.monitor.EtmPoint;

public class Problem {
	private static final EtmMonitor etmMonitor = EtmManager.getEtmMonitor();

	public static long RANDOM_SEED;
	public static boolean VERBOSE = true;
	public int M, P, S, L, RE, BO, N;
	List<Resource> resources;
	List<Machine> machines;
	List<Process> processes;
	List<Service> services;
	List<Location> locations;
	List<Neighborhood> neighborhoods;
	List<BalanceObjective> balanceObjectives;
	int weightProcessMoveCost;
	int weightServiceMoveCost;
	int weightMachineMoveCost;

	public int[][] MMC;

	// M x R capacity for resource r in machine m C(m,r)
	public int[][] C;
	public int[][] SC;
	// P x R
	public int[][] R;
	// P
	public int[] servicesOfProcesses;
	// M
	public int[] machines_locations;
	// M
	public int[] machines_neighborhoods;
	// S
	public List<Integer>[] service_dependencies;
	// S size
	List<Integer>[] servicesRequiredBy;

	List<Integer>[] processesListForServices;

	// PA Added for faster capacity validation
	// SRE index of simple resource, TRE index of transient resources
	public int[] SRE, TRE;

	// M X TRE
	public int[][] RC;

	public List<Integer>[][] neighborhoodsXlocations;
	public List<Integer>[] transientValidListOfProcessesByMachine;
	
	long lowerBound=0;
	public long[] lowerBoundLoadCostPerResource;

	public Problem() {
		resources = new ArrayList<Resource>();
		machines = new ArrayList<Machine>();
		processes = new ArrayList<Process>();
		services = new ArrayList<Service>();
		locations = new ArrayList<Location>();
		neighborhoods = new ArrayList<Neighborhood>();
		balanceObjectives = new ArrayList<BalanceObjective>();
	}

	public int getWeightProcessMoveCost() {
		return weightProcessMoveCost;
	}

	public void setWeightProcessMoveCost(int weightProcessMoveCost) {
		this.weightProcessMoveCost = weightProcessMoveCost;
	}

	public int getWeightServiceMoveCost() {
		return weightServiceMoveCost;
	}

	public void setWeightServiceMoveCost(int weightServiceMoveCost) {
		this.weightServiceMoveCost = weightServiceMoveCost;
	}

	public int getWeightMachineMoveCost() {
		return weightMachineMoveCost;
	}

	public void setWeightMachineMoveCost(int weightMachineMoveCost) {
		this.weightMachineMoveCost = weightMachineMoveCost;
	}

	public void addResource(Resource resource) {
		resource.setId("r" + resources.size());
		resources.add(resource);
	}

	public List<Resource> getResources() {
		return resources;
	}

	public void addMachine(Machine machine) {
		machine.setId(machines.size());
		machines.add(machine);
	}

	public List<Machine> getMachines() {
		return machines;
	}

	public void addService(Service service) {
		service.setId(services.size());
		services.add(service);
	}

	public Resource getResourceByIndex(int index) {
		return resources.get(index);
	}

	public List<Service> getServices() {
		return services;
	}

	@Deprecated
	public List<Service> getServicesOfProcesses(List<Integer> selectedProcesses) {
		List<Service> selected_services = new ArrayList<Service>();
		for (Integer p_id : selectedProcesses) {
			selected_services.add(services.get(getServiceIdForProcessId(p_id)));
		}
		return selected_services;
	}

	public void addProcess(Process process) {
		process.setId(processes.size());
		processes.add(process);
	}

	public List<Process> getProcesses() {
		return processes;
	}

	public List<BalanceObjective> getBalanceObjectives() {
		return balanceObjectives;
	}

	public void addBalanceObjective(BalanceObjective bo) {
		balanceObjectives.add(bo);
	}

	public List<Location> getLocations() {
		return locations;
	}

	public List<Neighborhood> getNeighborhoods() {
		return neighborhoods;
	}

	public List<Resource> getTransientResources() {
		List<Resource> trs = new ArrayList<Resource>();
		for (Resource resource : resources) {
			if (resource.isTransientUsage())
				trs.add(resource);
		}
		return trs;
	}

	public long getR(int p_index, int r_index) {
		return R[p_index][r_index];
	}

	public long getC(int m_index, int r_index) {
		return C[m_index][r_index];
	}

	public long getSC(int m_index, int r_index) {
		return SC[m_index][r_index];
	}

	public int getServiceIdForProcessId(int p_id) {
		Process aProcess = processes.get(p_id);
		return aProcess.getService();
	}

	public int getNeighborhoodIdForMachineId(int m_id) {
		Machine aMachine = machines.get(m_id);
		return aMachine.getNeighborhood();
	}

	public int getLocationIdForMachineId(int m_id) {
		Machine aMachine = machines.get(m_id);
		return aMachine.getLocation();
	}

	public List<Integer> getProcessesIdsForServiceId(int s_id) {
		return processesListForServices[s_id];
	}

	public List<Integer> getMachinesIdsForLocationId(int l_id) {
		Location aLocation = locations.get(l_id);
		return aLocation.getMachines();
	}

	public List<Integer> getMachinesIdsForNeighborhoodId(int n_id) {
		Neighborhood aNeighborhood = neighborhoods.get(n_id);
		return aNeighborhood.getMachines();
	}

	public void printDetails() {
		StringBuilder sb = new StringBuilder();
		sb.append("Resources =" + resources.size());
		sb.append("\n");
		for (Resource resource : resources) {
			sb.append(resource.toString());
			sb.append("\n");
		}
		sb.append("Machines  =" + machines.size());
		sb.append("\n");
		for (Machine machine : machines) {
			sb.append(machine.toString());
			sb.append("\n");
		}

		sb.append("Services  =" + services.size());
		sb.append("\n");
		for (Service service : services) {
			sb.append(service.toString());
			sb.append("\n");
		}

		sb.append("Processes  =" + processes.size());
		sb.append("\n");
		for (Process process : processes) {
			sb.append(process.toString());
			sb.append("\n");
		}

		sb.append("Locations  =" + locations.size());
		sb.append("\n");
		for (Location location : locations) {
			sb.append(location.toString());
			sb.append("\n");
		}

		sb.append("Neighborhoods  =" + neighborhoods.size());
		sb.append("\n");
		for (Neighborhood nei : neighborhoods) {
			sb.append(nei.toString());
			sb.append("\n");
		}

		sb.append("Balance Objectives =" + balanceObjectives.size());
		sb.append("\n");
		for (BalanceObjective bo : balanceObjectives) {
			sb.append(bo);
			sb.append("\n");
		}

		sb.append("\n");
		sb.append(String.format("weight process move cost=%d\n",
				weightProcessMoveCost));
		sb.append(String.format("weight service move cost=%d\n",
				weightServiceMoveCost));
		sb.append(String.format("weight machine move cost=%d\n",
				weightMachineMoveCost));
		System.out.println(sb.toString());

		calculateResourcesLB();

		printLocationNeighborhoodPattern();
	}

	@SuppressWarnings("unchecked")
	public void generateDataStructures() {
		C = new int[machines.size()][resources.size()];
		for (Machine machine : machines) {
			int m_i = machines.indexOf(machine);
			for (Resource resource : resources) {
				int r_i = resources.indexOf(resource);
				C[m_i][r_i] = machine.getCapacityFor(resource.getId());
			}
		}

		SC = new int[machines.size()][resources.size()];
		for (Machine machine : machines) {
			int m_i = machines.indexOf(machine);
			for (Resource resource : resources) {
				int r_i = resources.indexOf(resource);
				SC[m_i][r_i] = machine.getSafetyCapacityFor(resource.getId());
			}
		}

		R = new int[processes.size()][resources.size()];
		for (Process process : processes) {
			int p_i = processes.indexOf(process);
			for (Resource resource : resources) {
				int r_i = resources.indexOf(resource);
				R[p_i][r_i] = process.getRequirementFor(resource.getId());
			}
		}

		servicesOfProcesses = new int[processes.size()];
		for (Process process : processes) {
			int p_i = processes.indexOf(process);
			servicesOfProcesses[p_i] = process.service;
		}

		processesListForServices = new List[services.size()];
		for (int i = 0; i < services.size(); i++) {
			processesListForServices[i] = new ArrayList<Integer>();
		}
		for (int p_index = 0; p_index < processes.size(); p_index++) {
			int s_index = servicesOfProcesses[p_index];
			processesListForServices[s_index].add(p_index);
		}

		machines_locations = new int[machines.size()];
		for (Machine machine : machines) {
			int m_i = machines.indexOf(machine);
			machines_locations[m_i] = machine.location;
		}

		machines_neighborhoods = new int[machines.size()];
		for (Machine machine : machines) {
			int m_i = machines.indexOf(machine);
			machines_neighborhoods[m_i] = machine.neighborhood;
		}

		service_dependencies = new List[services.size()];
		for (Service aService : services) {
			int s_i = services.indexOf(aService);
			service_dependencies[s_i] = new ArrayList<Integer>();
			for (Integer b_service_id : aService.dependsOn) {
				service_dependencies[s_i].add(b_service_id);
			}
		}

		servicesRequiredBy = new List[S];

		for (int s = 0; s < S; s++) {
			servicesRequiredBy[s] = new ArrayList<Integer>();
		}
		for (int s = 0; s < S; s++) {
			for (Integer service_dep : service_dependencies[s]) {
				servicesRequiredBy[service_dep].add(s);
			}
		}

		MMC = new int[M][M];
		for (int i = 0; i < M; i++)
			for (int j = 0; j < M; j++)
				MMC[i][j] = machines.get(i).getMachineMoveCost(j);

		int countTrans = 0;
		for (int r = 0; r < RE; r++) {
			Resource resource = getResourceByIndex(r);
			if (resource.isTransientUsage()) {
				countTrans++;
			}
		}
		SRE = new int[RE - countTrans];
		TRE = new int[countTrans];
		for (int r = 0, sr = 0, tr = 0; r < RE; r++) {
			Resource resource = getResourceByIndex(r);
			if (resource.isTransientUsage())
				TRE[tr++] = r;
			else
				SRE[sr++] = r;
		}

		for (BalanceObjective bo : balanceObjectives) {
			bo.calcBalance(this);
		}

		neighborhoodsXlocations = new List[N][L];
		for (int n = 0; n < N; n++) {
			List<Integer> neighborhoodMachines = neighborhoods.get(n)
					.getMachines();
			for (int l = 0; l < L; l++) {
				neighborhoodsXlocations[n][l] = new ArrayList<Integer>();
				for (Integer m : locations.get(l).getMachines()) {
					if (neighborhoodMachines.contains(m))
						neighborhoodsXlocations[n][l].add(m);
				}
			}
		}
		
		calculateResourcesLB();
	}

	public void addLocation(int l, int m) {
		Location location = null;
		boolean found = false;
		for (Location loc : locations) {
			if (loc.getId() == l) {
				location = loc;
				found = true;
			}
		}
		if (!found) {
			location = new Location();
			location.setId(l);
			location.addMachine(m);
			locations.add(location);
		} else {
			location.addMachine(m);
		}
	}

	public void addNeighborhood(int n, int m) {
		Neighborhood neighborhood = null;
		boolean found = false;
		for (Neighborhood nei : neighborhoods) {
			if (nei.getId() == n) {
				neighborhood = nei;
				found = true;
			}
		}
		if (!found) {
			neighborhood = new Neighborhood();
			neighborhood.setId(n);
			neighborhood.addMachine(m);
			neighborhoods.add(neighborhood);
		} else {
			neighborhood.addMachine(m);
		}
	}

	public String getCondensedInfo() {
		int x;
		int max = 0;
		int min = Integer.MAX_VALUE;
		int sum = 0;
		for (Service aService : services) {
			x = aService.getProcesses().size();
			sum += x;
			if (x > max)
				max = x;
			if (x < min)
				min = x;
		}

		int max2 = 0;
		int min2 = Integer.MAX_VALUE;
		int sum2 = 0;
		for (Location aLocation : locations) {
			x = aLocation.getMachines().size();
			sum2 += x;
			if (x > max2)
				max2 = x;
			if (x < min2)
				min2 = x;
		}

		int max3 = 0;
		int min3 = Integer.MAX_VALUE;
		int sum3 = 0;
		for (Neighborhood aNeighborhood : neighborhoods) {
			x = aNeighborhood.getMachines().size();
			sum3 += x;
			if (x > max3)
				max3 = x;
			if (x < min3)
				min3 = x;
		}

		int transient_resources = 0;
		for (Resource aResource : resources) {
			if (aResource.isTransientUsage())
				transient_resources++;
		}

		int sum_dependencies = 0;
		int max_in = 0;
		int max_out = 0;
		for (Service aService : services) {
			sum_dependencies += aService.dependsOn.size();
			if (aService.getDependedBy().size() > max_in)
				max_in = aService.getDependedBy().size();
			if (aService.getDependsOn().size() > max_out)
				max_out = aService.getDependsOn().size();
		}

		double avg_dep = (double) sum_dependencies / services.size();

		// PPS = Processes Per Service
		// MPL = Machines Per Location
		// MPN = Machines Per Neighborhood
		StringBuilder sb = new StringBuilder();
		sb.append(String
				.format("P=%d,\tM=%d,\tR=%d,\tTR=%d, \tS=%d,\tL=%d,\tN=%d,\tBO=%d,\tWPMC=%d,\tWSMC=%d,\tWMMC=%d,\t[MIN|MAX|AVG PPS=%d|%d|%.2f\tMPL=%d|%d|%.2f\tMPN=%d|%d|%.2f],\t DEPS_MAX_IN=%d DEPS_MAX_OUT=%d DEPS_AVG=%.2f",
						processes.size(), machines.size(), resources.size(),
						transient_resources, services.size(), locations.size(),
						neighborhoods.size(), balanceObjectives.size(),
						getWeightProcessMoveCost(), getWeightServiceMoveCost(),
						getWeightMachineMoveCost(), min, max, (double) sum / S,
						min2, max2, sum2 / (double) L, min3, max3, sum3
								/ (double) N, max_in, max_out, avg_dep));
		return sb.toString();
	}

	public void clearEligibleMachines() {
		for (int p = 0; p < P; p++) {
			Process proc = getProcesses().get(p);
			proc.clearEligibleMachines();
		}

	}

	public void apiDemo(int p_id, int m_id, int s_id, int l_id, int n_id) {
		System.out
				.println("#######################problem API Demo#####################");
		System.out.printf("Process p%d belongs to s%d\n", p_id,
				getServiceIdForProcessId(p_id));
		System.out.printf("Machine m%d is in neighborhood n%d\n", m_id,
				getNeighborhoodIdForMachineId(m_id));
		System.out.printf("Machine m%d is in location l%d\n", m_id,
				getLocationIdForMachineId(m_id));
		System.out.printf("Service s%d has processes %s\n", s_id,
				getProcessesIdsForServiceId(s_id));
		System.out.printf("Location l%d has machines %s\n", l_id,
				getMachinesIdsForLocationId(l_id));
		System.out.printf("Neighborhood l%d has machines %s\n", l_id,
				getMachinesIdsForNeighborhoodId(n_id));
		System.out
				.println("############################################################");
	}

	public void sortCollections() {
		Collections.sort(locations, new Comparator<Location>() {
			public int compare(Location loc1, Location loc2) {
				return loc1.id - loc2.id;
			}
		});
		Collections.sort(neighborhoods, new Comparator<Neighborhood>() {
			public int compare(Neighborhood n1, Neighborhood n2) {
				return n1.id - n2.id;
			}
		});

	}

	public boolean isServiceDependedEitherWay(int s_id) {
		Service aService = services.get(s_id);
		if (!aService.dependsOn.isEmpty())
			return true;
		for (int s = 0; s < S; s++) {
			Service aService2 = services.get(s);
			if (aService2.dependsOn.contains(new Integer(s_id)))
				return true;
		}
		return false;
	}

	public List<Integer> getProcessesFromSameService(
			List<Integer> listOfProcesses) {
		List<Integer> processes = new ArrayList<Integer>();
		for (Integer p_id : listOfProcesses) {
			int s_id = getServiceIdForProcessId(p_id);
			for (Integer p_id2 : listOfProcesses) {
				if (p_id.intValue() != p_id2.intValue()) {
					int s_id2 = getServiceIdForProcessId(p_id2);
					if (s_id == s_id2)
						processes.add(p_id);
				}
			}
		}
		return processes;
	}

	public void printEligibleMachinesForProcesses(
			List<Integer> selectedprocesses) {
		for (Integer sp_id : selectedprocesses) {
			Process aProcess = processes.get(sp_id);
			Collections.sort(aProcess.getEligibleMachines());
			System.out.printf("p=%d --> %s\n", sp_id,
					aProcess.getEligibleMachines());
		}
	}

	int[][] ordered_processids_by_resources_needs;
	int[] ordered_processids_by_total_resources_needs;
	int[][] ordered_machineids_by_resources_capacity;
	int[] ordered_machineids_by_total_resources_capacities;

	public void createOrderedByResourcesArrays() {
		ordered_processids_by_resources_needs = new int[P][RE];
		for (int r = 0; r < RE; r++) {
			int[] R_COPY = new int[P];
			for (int p = 0; p < P; p++) {
				R_COPY[p] = R[p][r];
				ordered_processids_by_resources_needs[p][r] = p;
			}
			sort(R_COPY, r, ordered_processids_by_resources_needs);
		}
		// for (int r = 0; r < RE; r++) {
		// System.out.println("Resource " + r);
		// for (int i = 0; i < P; i++) {
		// int p = ordered_processids_by_resources_needs[i][r];
		// Process aProcess = getProcesses().get(p);
		// System.out.println(aProcess.toString());
		// }
		// }

		ordered_processids_by_total_resources_needs = new int[P];
		int[] R_COPY = new int[P];
		for (int p = 0; p < P; p++) {
			ordered_processids_by_total_resources_needs[p] = p;
			for (int r = 0; r < RE; r++)
				R_COPY[p] += R[p][r];
		}

		System.out.println("");
		sort2(R_COPY, ordered_processids_by_total_resources_needs);
		// for (int i = 0; i < P; i++) {
		// int p = ordered_processids_by_total_resources_needs[i];
		// Process aProcess = getProcesses().get(p);
		// System.out.println(aProcess.toString());
		// }

		ordered_machineids_by_resources_capacity = new int[M][RE];
		for (int r = 0; r < RE; r++) {
			int[] C_COPY = new int[M];
			for (int m = 0; m < M; m++) {
				C_COPY[m] = C[m][r];
				ordered_machineids_by_resources_capacity[m][r] = m;
			}
			sort(C_COPY, r, ordered_machineids_by_resources_capacity);
		}
		// for (int r = 0; r < RE; r++) {
		// System.out.println("Resource " + r);
		// for (int i = 0; i < M; i++) {
		// int m = ordered_machineids_by_resources_capacity[i][r];
		// Machine aMachine = getMachines().get(m);
		// System.out.println(aMachine.capacityString());
		// }
		// }

		ordered_machineids_by_total_resources_capacities = new int[M];
		int[] C_COPY = new int[M];
		for (int m = 0; m < M; m++) {
			ordered_machineids_by_total_resources_capacities[m] = m;
			for (int r = 0; r < RE; r++)
				C_COPY[m] += C[m][r];
		}
		System.out.println("");
		sort2(C_COPY, ordered_machineids_by_total_resources_capacities);
		// for (int i = 0; i < M; i++) {
		// int m = ordered_machineids_by_total_resources_capacities[i];
		// Machine aMachine = getMachines().get(m);
		// System.out.println(aMachine.capacityString());
		// }

	}

	void sort(int[] cc, int r, int[][] a) {
		for (int i = 1; i < cc.length; i++) {
			for (int j = cc.length - 1; j >= i; j--) {
				if (cc[j - 1] < cc[j]) {
					int temp1 = cc[j];
					cc[j] = cc[j - 1];
					cc[j - 1] = temp1;
					int temp2 = a[j][r];
					a[j][r] = a[j - 1][r];
					a[j - 1][r] = temp2;
				}
			}
		}
	}

	void sort2(int[] cc, int[] a) {
		for (int i = 1; i < cc.length; i++) {
			for (int j = cc.length - 1; j >= i; j--) {
				if (cc[j - 1] < cc[j]) {
					int temp1 = cc[j];
					cc[j] = cc[j - 1];
					cc[j - 1] = temp1;
					int temp2 = a[j];
					a[j] = a[j - 1];
					a[j - 1] = temp2;
				}
			}
		}
	}

	public List<Integer> fakeMachineIdsOrderedByLocation = new ArrayList<Integer>();
	public List<Integer> fakeMachineIdsOrderedByNeighborhood = new ArrayList<Integer>();

	public void createMachinesOrderedListsByLocationAndNeighborhood() {
		int[][] a = new int[M][2];
		for (int i = 0; i < M; i++) {
			a[i][0] = i;
			Machine aMachine = getMachines().get(i);
			a[i][1] = aMachine.getLocation();
		}
		for (int i = 1; i < M; i++) {
			for (int j = M - 1; j >= i; j--) {
				if (a[j - 1][1] > a[j][1]) {
					int temp = a[j - 1][0];
					a[j - 1][0] = a[j][0];
					a[j][0] = temp;
					temp = a[j - 1][1];
					a[j - 1][1] = a[j][1];
					a[j][1] = temp;
				}
			}
		}
		for (int i = 0; i < M; i++) {
			fakeMachineIdsOrderedByLocation.add(a[i][0]);
		}
		for (int i = 0; i < M; i++) {
			a[i][0] = i;
			Machine aMachine = getMachines().get(i);
			a[i][1] = aMachine.getNeighborhood();
		}
		for (int i = 1; i < M; i++) {
			for (int j = M - 1; j >= i; j--) {
				if (a[j - 1][1] > a[j][1]) {
					int temp = a[j - 1][0];
					a[j - 1][0] = a[j][0];
					a[j][0] = temp;
					temp = a[j - 1][1];
					a[j - 1][1] = a[j][1];
					a[j][1] = temp;
				}
			}
		}
		for (int i = 0; i < M; i++) {
			fakeMachineIdsOrderedByNeighborhood.add(a[i][0]);
		}
	}

	DirectedGraph<String, DefaultEdge> directedGraph;

	public void generateDependencyGraph() {
		directedGraph = new DefaultDirectedGraph<String, DefaultEdge>(
				DefaultEdge.class);
		Set<Integer> vertices = new HashSet<Integer>();
		for (Service aService : services) {
			if (!aService.getDependsOn().isEmpty()) {
				vertices.add(aService.id);
				vertices.addAll(aService.getDependsOn());
			}
		}

		for (Integer v : vertices) {
			directedGraph.addVertex(getVertexLabel(v));
		}

		for (Integer servicea_id : vertices) {
			Service aService = services.get(servicea_id);
			if (!aService.getDependsOn().isEmpty()) {
				for (Integer serviceb_id : aService.getDependsOn()) {
					directedGraph.addEdge(getVertexLabel(aService.id),
							getVertexLabel(serviceb_id));
				}
			}
		}

		// System.out.printf("V=%s \nE=%s\n", directedGraph.vertexSet(),
		// directedGraph.edgeSet());
	}

	private String getVertexLabel(int service_id) {
		Service aService = services.get(service_id);
		return String.format("s%d_p%d_d%d", service_id, aService.getProcesses()
				.size(), aService.getDependsOn().size());
	}

	public DirectedGraph<String, DefaultEdge> getDirectedGraph() {
		return directedGraph;
	}

	public void calculateResourcesLB() {
		long[] reqRE = new long[RE];
		long[] availRE = new long[RE];
		long[] availSCRE = new long[RE];
		lowerBoundLoadCostPerResource = new long[RE];
		for (int r = 0; r < RE; r++){
			boolean isTrans = getResourceByIndex(r).isTransientUsage();
			for (int p = 0; p < P; p++) {
				reqRE[r] += R[p][r];
			}
		}

		for (int m = 0; m < M; m++) {
			for (int r = 0; r < RE; r++) {
				availRE[r] += C[m][r];
				availSCRE[r] += SC[m][r];
			}
		}

		long LB_cost_lb = 0;
		for (int r = 0; r < RE; r++) {
			lowerBoundLoadCostPerResource[r] += Math.max(0, (reqRE[r] - availSCRE[r]));
			LB_cost_lb += lowerBoundLoadCostPerResource[r] * resources.get(r).getWeightLoadCost();
		}
//		System.out.println("LB_cost_lb="+LB_cost_lb);
				
		double spreadDifficulty = 0.0, dependsDifficulty = 0.0;
		for(int s=0; s<S;s++){
			Service ser = services.get(s);
			double diff = 1-((this.L - ser.getSpreadMin())/ (double)L);
			spreadDifficulty += diff;
			dependsDifficulty += ((ser.dependsOn.size() + ser.dependedBy.size())*(ser.processes.size()/(double)P));
		}
		spreadDifficulty/=S;
		dependsDifficulty/=S;
//		System.out.println("SD="+spreadDifficulty+", DD="+dependsDifficulty);
				
	    long BC_cost_lb=0;
			for(int bo=0;bo<BO;bo++){
				BalanceObjective b = balanceObjectives.get(bo);
				BC_cost_lb += Math.max(0,
								(availRE[b.resourcea]-reqRE[b.resourcea])*b.target-
								(availRE[b.resourceb]-reqRE[b.resourceb])
								
						)*b.weightBalanceCost;
//				System.out.println("BC_cost_lb="+BC_cost_lb);
			}
		
		lowerBound =(long)(1+spreadDifficulty + dependsDifficulty)*(LB_cost_lb+BC_cost_lb);

//		System.err.println("LB=" + lowerBound);
//		System.err.println(Arrays.toString(lowerBoundLoadCostPerResource));
	}

	public boolean hasBalanceObjectives() {
		if (balanceObjectives.isEmpty())
			return false;
		else
			return true;
	}

	public List<Integer> getEligibleMachinesFor(int p) {
		return getProcesses().get(p).getEligibleMachines();
	}

	public void printLocationNeighborhoodPattern() {
		int l = 0;
		System.out.print("L     N\t");
		for (int i = 0; i < neighborhoods.size(); i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		int[][] ln = new int[locations.size()][neighborhoods.size()];
		for (Location aLocation : locations) {
			List<Integer> lm = aLocation.getMachines();
			System.out.print(l + "\t");
			for (Integer m : lm) {
				ln[l][getNeighborhoodIdForMachineId(m)]++;
			}
			for (int i = 0; i < neighborhoods.size(); i++) {
				System.out.print(ln[l][i] + "\t");
			}
			System.out.println();
			l++;
		}
	}

	public String getSelectedProcessesAndEligibleMachines(
			List<Integer> selectedProcesses, boolean expanded,
			SolverEnvironment env) {
		Set<Integer> machines = new HashSet<Integer>();
		StringBuilder sb = new StringBuilder();
		int xvars = 0;
		for (Integer p : selectedProcesses) {
			Process aProcess = getProcesses().get(p);
			xvars += aProcess.getEligibleMachines().size();
			machines.addAll(aProcess.getEligibleMachines());
		}
		int i = 0;
		for (Integer p : selectedProcesses) {
			Process aProcess = getProcesses().get(p);
			i++;
			if ((!expanded) && (i >= 5)) {
				sb.append(String.format("and %d others...\n",
						selectedProcesses.size() - i));
				break;
			} else {
				Collections.sort(aProcess.getEligibleMachines());
				int im = env.getCurrentSolution().getMachineIdForProcessId(p);
				int cm = env.getInitialSolution().getMachineIdForProcessId(p);
				int s = getServiceIdForProcessId(p);
				int nei = env.getCurrentSolution().getNeighBorhoodIdForProcess(p);
				sb.append(String.format("%d) p%d_s%s_im%d_cm%d_n%d --> %s\n", i, p,
						s, im, cm, nei, aProcess.getEligibleMachines()));
			}
		}

		sb.append(String.format("XVARS=%d PROCESSES=%d MACHINES=%d", xvars,
				selectedProcesses.size(), machines.size()));
		return sb.toString();
	}

	@Deprecated
	public void printSelectedProcessesAndEligibleMachines(
			List<Integer> selectedProcesses, boolean expanded,
			SolverEnvironment env) {
		Set<Integer> machines = new HashSet<Integer>();
		StringBuilder sb = new StringBuilder();
		int xvars = 0;
		for (Integer p : selectedProcesses) {
			Process aProcess = getProcesses().get(p);
			xvars += aProcess.getEligibleMachines().size();
			machines.addAll(aProcess.getEligibleMachines());
		}
		int i = 0;
		for (Integer p : selectedProcesses) {
			Process aProcess = getProcesses().get(p);
			i++;
			if ((!expanded) && (i >= 5)) {
				sb.append(String.format("and %d others...\n",
						selectedProcesses.size() - i));
				break;
			} else {
				Collections.sort(aProcess.getEligibleMachines());
				int im = env.getCurrentSolution().getMachineIdForProcessId(p);
				int cm = env.getInitialSolution().getMachineIdForProcessId(p);
				sb.append(String.format("%d) p%d_im%d_cm%d --> %s\n", i, p, im,
						cm, aProcess.getEligibleMachines()));
			}
		}

		sb.append(String.format("XVARS=%d PROCESSES=%d MACHINES=%d\n", xvars,
				selectedProcesses.size(), machines.size()));
		System.out.println(sb.toString());
	}

	public void updateServiceDependedByDependencies() {
		for (Service aService : services) {
			for (Integer sb : aService.getDependsOn()) {
				Service bService = services.get(sb);
				bService.addDependedBy(aService.getId());
			}
		}
	}

	public void computeTransientResourcesRemainingCapacityPerMachine(
			SolverEnvironment env) {
		RC = new int[M][TRE.length];
		for (int i = 0; i < M; i++) {
			List<Integer> processes = env.getInitialSolution()
					.getProcessesForMachine(i);
			for (int j = 0; j < RC[i].length; j++) {
				int r = TRE[j];
				RC[i][j] = C[i][r];
				for (Integer p : processes) {
					RC[i][j] -= R[p][r];
				}
			}
		}
	}
	
	public long getLowerBound(){return lowerBound;}

//	public void computeMachinesEligibleProcessesLists(SolverEnvironment env) {
//		EtmPoint point = etmMonitor
//				.createPoint("Problem:generateMachinesEligibleProcessesLists");
//		transientValidListOfProcessesByMachine = new List[M];
//		for (int m = 0; m < M; m++) {
//			transientValidListOfProcessesByMachine[m] = new ArrayList<Integer>();
//			for (int p = 0; p < P; p++) {
//				if (!env.getIllegalMachines(p).contains(m)) {
//					transientValidListOfProcessesByMachine[m].add(p);
//				}
//			}
//		}
//		point.collect();
//	}

}
